Матч 315, Сумма цифр (DigitsSum)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

По заданному целому неотрицательному числу ищется его сумма цифр. Если сумма больше 9, то снова ищется ее сумма цифр. Процесс продолжается до тех пор, пока очередная сумма не станет меньше 10. Необходимо найти значение этой последней суммы.

Например, для числа 12345 сумма цифр равна 1 + 2 + 3 + 4 + 5 = 15. Ищем сумму цифр числа 15. Она равна 1 + 5 = 6. Результатом будет 6.

Класс: DigitsSum

Метод: int lastDigit(int n)

Ограничения: 0 £ n £ 2147483647.

Вход. Натуральное число n.

Выход. Окончательная сумма, которая получится после применения над числом n описанной выше процедуры.

Пример входа

n

12345

6

314

Пример выхода

6

6

8

РЕШЕНИЕ

математика

Обозначим сумму цифр числа n через S(n). Число n делится на 9 тогда и только тогда, когда S(n) делится на 9. В задаче требуется найти значение S(S(…S(n)…)), которое меньше 10. Оно равно n mod 9, так как числа n и S(S(…S(n)…)) дают одинаковый остаток при делении на 9. При этом если входное значение n = 0, то результат равен 0. Если n > 0 и n mod 9 = 0, то результирующее значение равно 9.

Искомую сумму можно также вычислить при помощи выражения (n – 1) % 9 + 1.

ПРОГРАММА

#include <stdio.h>

class DigitsSum

{

public:

int lastDigit(int n)

{

if (!n) return 0;

if (n % 9 == 0) return 9;

return n % 9;

}

};

Упрощенный вариант решения задачи:

#include <stdio.h>

class DigitsSum

{

public:

int lastDigit(int n)

{

return (n-1) % 9 + 1;

}

};